#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, d;
int que[N],que2[N];

struct point{
    int x,y;
}p[N];

int check(int x){
    int hh1 = 0, hh2 = 0, tt1 = -1, tt2 = -1;
    for(int i = 1; i <= n; i++){
        while(hh1 <= tt1 && p[i].x - p[que[hh1]].x > x) hh1++;
        while(hh2 <= tt2 && p[i].x - p[que2[hh2]].x > x) hh2++;

        while(hh1 <= tt1 && p[que[tt1]].y > p[i].y) tt1--;
        while(hh2 <= tt2 && p[que2[tt2]].y < p[i].y) tt2--;

        que[++tt1] = i;
        que2[++tt2] = i;
        if(p[que2[hh2]].y - p[que[hh1]].y >= d){
            // cout << p[que2[hh2]].x <<" " << p[que2[hh2]].y <<'\n';
            // cout << p[que[hh1]].x <<" " << p[que[hh1]].y <<'\n';
            return true;
        } 
    }

    return false;
}

bool cmp(point a,point b){
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

int main()
{
    cin >> n >> d;
    for (int i = 1; i <= n; i++){
         cin >> p[i].x >> p[i].y;
    }

    sort(p+1, p+ 1 + n,cmp);
    // cout << check(2);
    int l = 0, r = 1000001,ans = -1;
    while (l < r){
        int mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid;
        else l = mid + 1;
    }
    cout << ans;
    return 0;
}
